package com.jia.leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 1455. 检查单词是否为句中其他单词的前缀
 */
public class Pro1455 {
    final static int R = 26; //26小写字母
    class TrieNode {
        TrieNode[] links;
        boolean isEnd;
        List<Integer> index; //记录单词下标,可能有重复的word
        public TrieNode(){
            links = new TrieNode[R];
        }
    }

    TrieNode root = new TrieNode();
    //Insert a work into the trie
    //Time:O(m) m is the length of the key.

    /**
     * @param word work
     * @param index index  1..n
     */
    public void insert(String word, int index) {
        TrieNode node = root;
        for(int i = 0; i < word.length(); i++) {
            char currentChar = word.charAt(i);
            if(node.links[currentChar - 'a'] == null) {
                node.links[currentChar - 'a'] = new TrieNode();
            }
            node = node.links[currentChar - 'a'];
        }
        node.isEnd = true;
        node.index = node.index == null ? new ArrayList<Integer>() : node.index;
        node.index.add(index);
    }


    //search a prefix or whole key in trie and
    //returns the node where search ends
    //Time:O(m)  m is the length of the word
    private TrieNode searchPrefix(String word) {
        TrieNode node = root;
        for(int i = 0; i < word.length(); i++) {
            char currentChar = word.charAt(i);
            if(node.links[currentChar - 'a'] != null) {
                node = node.links[currentChar - 'a'];
            }else {
                return null;
            }
        }
        return node;
    }
    int ans = -1;
    //题目返回下标最小的一个单词下标,dfs所有的符合前缀的word的下标
    private void searchIndex(TrieNode trieNode) {
        if(trieNode == null){ return; }
        if(trieNode.isEnd) {
            if(ans == -1) {
                ans = minIndex(trieNode.index);
            }else {
                ans = minIndex(trieNode.index, ans);
            }
        }
        for (int i = 0; i < 26; i++) {
            if (trieNode.links[i] != null) {
                searchIndex(trieNode.links[i]);
            }
        }
    }
    private int minIndex(List<Integer> list) {
        if(list == null) { return -1;}
        int min = list.get(0);
        for(int i = 1; i < list.size(); i++) {
            min = Math.min(min, list.get(i));
        }
        return min;
    }
    private int minIndex(List<Integer> list, Integer value) {
        if(list == null) { return -1; }
        list.add(value);
        return minIndex(list);
    }

    public int isPrefixOfWord(String sentence, String searchWord) {
        String[] words = sentence.split(" ");
        //建立trie树
        for(int i = 0; i < words.length; i++) {
            insert(words[i], i + 1);
        }
        TrieNode trieNode = searchPrefix(searchWord);
        //统计单词个数
        searchIndex(trieNode);
        return ans;
    }

    public static void main(String[] args) {
        Pro1455 pro1455 = new Pro1455();
        String sentence = "this problem is an easy problem";
        String searchWord = "pro";
        System.out.println(pro1455.isPrefixOfWord(sentence, searchWord));;
    }

}
